package com.mlamp.二叉树;

import java.lang.annotation.Native;
import java.lang.reflect.WildcardType;

public class 最大路径和 {


    int maxSum = Integer.MIN_VALUE;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        最大路径和 instance = new 最大路径和();
        int i = instance.maxPathSum(root);
        System.out.println(i);

        instance.maxSum = Integer.MIN_VALUE;
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(2);
        int i1 = instance.maxPathSum(root1);
        System.out.println(i1);

        instance.maxSum = Integer.MIN_VALUE;
        System.out.println(" root -------------------------");
        i1 = instance.maxGainD(root);
        System.out.println(instance.maxSum);

        instance.maxSum = Integer.MIN_VALUE;
        System.out.println("root1 --------------------------");
        i1 = instance.maxGainD(root1);
        System.out.println(instance.maxSum);

    }


    public int maxGainD(TreeNode root) {
        if (root == null) return 0;
        int leftGain = Math.max(maxGainD(root.left), 0);
        int rightGain = Math.max(maxGainD(root.right), 0);
        maxSum = Math.max(maxSum, leftGain + rightGain + root.val);
        return Math.max(leftGain, rightGain) + root.val;
    }


    /**
     * 二叉树求最大路径和
     *
     * @param root
     * @return
     */

    public int maxGain5(TreeNode root) {
        if (root == null) return 0;
        int leftGain = Math.max(maxGain5(root.left), 0);
        int rightGain = Math.max(maxGain5(root.right), 0);
        int weight = root.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, weight);
        return root.val + Math.max(leftGain, rightGain);
    }

    public int maxGain4(TreeNode root) {
        if (root == null) return 0;
        int leftGain = Math.max(maxGain4(root.left), 0);
        int rightGain = Math.max(maxGain4(root.right), 0);
        int weight = root.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, weight);
        return root.val + Math.max(leftGain, rightGain);
    }


    private static int RESULT = Integer.MIN_VALUE;

    public int maxGainA(TreeNode root) {
        if (root == null) return 0;
        int leftGain = Math.max(maxGainA(root.left), 0);
        int rightGain = Math.max(maxGainA(root.right), 0);
        int weight = leftGain + root.val + rightGain;
        RESULT = Math.max(weight, RESULT);
        return root.val + Math.max(leftGain, rightGain);
    }

    public int maxGainB(TreeNode root) {
        if (root == null) return 0;
        int leftGain = Math.max(maxGainB(root.left), 0);
        int rightGain = Math.max(maxGainB(root.right), 0);
        int weight = leftGain + root.val + rightGain;
        RESULT = Math.max(RESULT, weight);
        return root.val + Math.max(leftGain, rightGain);
    }


    public int maxGain2(TreeNode root) {
        if (root == null) return 0;
        int leftGain2 = Math.max(maxGain2(root.left), 0);
        int rightGain2 = Math.max(maxGain2(root.right), 0);
        int weightPath = root.val + leftGain2 + rightGain2;
        maxSum = Math.max(maxSum, weightPath);
        return root.val + Math.max(leftGain2, rightGain2);
    }


    public int maxGain3(TreeNode root) {
        if (root == null) return 0;
        int leftGain = Math.max(maxGain3(root.left), 0);
        int rightGain = Math.max(maxGain3(root.right), 0);
        int weighPath = root.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, weighPath);
        return root.val + Math.max(leftGain, rightGain);
    }


    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }


    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


}


